package cn.demoncat.util.lang;

import cn.demoncat.util.lang.constant.StringConstant;
import cn.demoncat.util.lang.entity.tree.TreeEntity;
import cn.demoncat.util.lang.entity.tree.TreeSortComparator;
import cn.demoncat.util.lang.fn.Consumer2;
import org.apache.commons.collections4.CollectionUtils;
import org.apache.commons.lang3.StringUtils;

import java.util.*;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.function.Predicate;
import java.util.stream.Collectors;

/**
 * 描述：树形结构处理工具
 *
 * @author 延晓磊
 *
 * @since 2017年6月12日
 */
public class TreeUtil {

	/**
	 * 转换List为树
	 *
	 * @param list				源数据，结果顺序一致
	 * @param idGetter			获取ID
	 * @param parentIdGetter	获取ParentId
	 * @param childrenSetter	设置ChildrenList
	 * @param rootPredicate		判断是否为根节点
	 * @param <E>	数据类型
	 * @param <P>	ID类型
	 * @return	树列表
	 *
	 * @author 延晓磊
	 * @since 2021年04月23日
	 */
	public static <E,P> List<E> getTree(List<E> list, Function<E,P> idGetter, Function<E,P> parentIdGetter, Consumer2<E,List<E>> childrenSetter, Predicate<E> rootPredicate){
		// 根列表
		List<E> root = new ArrayList<>();
		if (CollectionUtils.isNotEmpty(list)) {
			// 数据缓存
			Map<P,List<E>> map = new HashMap<>();
			List<E> children;
			for (E e : list) {
				// 初始化子节点
				children = new ArrayList<>();
				childrenSetter.accept(e, children);
			    // 加入缓存
				map.put(idGetter.apply(e), children);
			}
			for (E e : list) {
				if (rootPredicate.test(e)) {
					// 保存根节点
					root.add(e);
				}else {
					// 保存子节点
					children = map.get(parentIdGetter.apply(e));
					if (children != null) {
						children.add(e);
					}
					// 没有父节点 > 丢弃
				}
			}
		}
		return root;
	}

	/**
	 * 转换List为树
	 *
	 * @param list		源数据，结果顺序一致
	 * @param rootId	根ID
	 * @param <E>	数据类型
	 * @param <P>	ID类型
	 * @return	树列表
	 *
	 * @author 延晓磊
	 * @since 2021年04月23日
	 */
	public static <E extends TreeEntity<E,P>,P> List<E> getTree(List<E> list, P rootId){
		return getTree(list, TreeEntity::getId, TreeEntity::getParentId, TreeEntity::setChildren, o -> rootId == null ? o.getParentId() == null : o.getParentId().equals(rootId));
	}

	/**
	 * 将列表转换为树
	 *
	 * @param list		列表
	 * @param rootId	根节点
	 * @param checks	选择的节点ID
	 * @param comparator	排序器
	 *
	 * @return [o[children]]
	 *
	 * @author 延晓磊
	 * @since 2017年6月12日
	 */
	public static <T extends TreeEntity<T, P>,P> List<T> getTree(List<T> list, P rootId, Collection<P> checks, Comparator<T> comparator) {
		// 为空
		if(CollectionUtils.isEmpty(list)){
			return new ArrayList<>(0);
		}
		// 选中
		if(CollectionUtils.isNotEmpty(checks)){
			list.forEach(o -> {
				if (checks.contains(o.getId())) {
					o.setChecked(1);
				}
			});
		}
		// 排序
		if(comparator != null){
			list.sort(comparator);
		}
		// 树
		return getTree(list, rootId);
	}

	/**
	 * 将列表转换为树
	 *
	 * @param list		列表
	 * @param rootId	根节点
	 * @param comparator	排序器
	 *
	 * @return [o[children]]
	 *
	 * @author 延晓磊
	 * @since 2017年6月12日
	 */
	public static <T extends TreeEntity<T, P>,P> List<T> getTree(List<T> list, P rootId, Comparator<T> comparator) {
		return getTree(list, rootId, null, comparator);
	}

	/**
	 * 将列表转换为树 - 根据sort排序
	 *
	 * @param list		列表
	 * @param rootId	根节点
	 *
	 * @return [o[children]]
	 *
	 * @author 延晓磊
	 * @since 2017年6月12日
	 */
	public static <T extends TreeEntity<T, P>,P> List<T> getSortedTree(List<T> list, P rootId) {
		return getTree(list, rootId, TreeSortComparator.get());
	}

	/**
	 * 将列表转换为树 - 带选择框(checked==1)，默认顺序
	 * 
	 * @param list		列表
	 * @param rootId  	根节点
	 * @param checks  	选择的节点ID
	 *
	 * @return [o[children]]
	 * 
	 * @author 延晓磊
	 *
	 * @since 2017年6月12日
	 */
	public static <T extends TreeEntity<T, P>,P> List<T> getCheckTree(List<T> list, P rootId, Collection<P> checks) {
		return getTree(list, rootId, checks, null);
	}

	/**
	 * 将列表转换为树 - 带选择框(checked==1)，根据sort排序
	 *
	 * @param list		列表
	 * @param checks  	选择的节点ID
	 * @param rootId  	根节点
	 *
	 * @return [o[children]]
	 *
	 * @author 延晓磊
	 *
	 * @since 2017年6月12日
	 */
	public static <T extends TreeEntity<T, P>,P> List<T> getSortedCheckTree(List<T> list, P rootId, Collection<P> checks) {
		return getTree(list, rootId, checks, TreeSortComparator.get());
	}

	/**
	 * 将列表转换为树，多层级并列
	 *
	 * @param list		列表
	 * @param rootId 	根节点
	 * @param comparator	排序器
	 * 
	 * @return [o] 树形数据(多层级并列)
	 * 
	 * @author 延晓磊
	 *
	 * @since 2017年6月12日
	 */
	public static <T extends TreeEntity<T, P>,P> List<T> getTreeList(List<T> list, P rootId, Comparator<T> comparator) {
		// 获取树型整理的list
		List<T> tree = getTree(list, rootId, comparator);
		// 并排
		return toList(tree);
	}

	/**
	 * 将列表转换为树，多层级并列 - 默认顺序
	 *
	 * @param list		列表
	 * @param rootId 	根节点
	 *
	 * @return [o] 树形数据(多层级并列)
	 *
	 * @author 延晓磊
	 *
	 * @since 2017年6月12日
	 */
	public static <T extends TreeEntity<T, P>,P> List<T> getTreeList(List<T> list, P rootId) {
		return getTreeList(list, rootId, null);
	}

	/**
	 * 将列表转换为树，多层级并列 - 根据sort排序
	 *
	 * @param list		列表
	 * @param rootId 	根节点
	 *
	 * @return [o] 树形数据(多层级并列)
	 *
	 * @author 延晓磊
	 *
	 * @since 2017年6月12日
	 */
	public static <T extends TreeEntity<T, P>,P> List<T> getSortedTreeList(List<T> list, P rootId) {
		return getTreeList(list, rootId, TreeSortComparator.get());
	}

	/**
	 * 将列表转换为树，多层级并列名称
	 *
	 * @param list		列表
	 * @param rootId 	根节点
	 * @param comparator	排序器
	 * @param rootName	根节点名称：默认null
	 *
	 * @return {'id':name} 树形数据(多层级并列)
	 *
	 * @author 延晓磊
	 *
	 * @since 2017年6月12日
	 */
	public static <T extends TreeEntity<T, P>,P> Map<String, String> getTreeNameMap(List<T> list, P rootId, Comparator<T> comparator, String rootName) {
		// 获取树型整理的list
		List<T> tree = getTree(list, rootId, comparator);
		// 并排树节点并组合名称
		Map<String,String> map = new LinkedHashMap<>();
		addChildName(map, tree, rootName);
		return map;
	}

	/**
	 * 将列表转换为树，多层级并列名称 - 默认顺序
	 *
	 * @param list		列表
	 * @param rootId 	根节点
	 * @param rootName	根节点名称：默认null
	 *
	 * @return {'id':name} 树形数据(多层级并列)
	 *
	 * @author 延晓磊
	 *
	 * @since 2017年6月12日
	 */
	public static <T extends TreeEntity<T, P>,P> Map<String, String> getTreeNameMap(List<T> list, P rootId, String rootName) {
		return getTreeNameMap(list, rootId, null, rootName);
	}

	/**
	 * 将列表转换为树，多层级并列名称 - 默认顺序
	 *
	 * @param list		列表
	 * @param rootId 	根节点
	 *
	 * @return {'id':name} 树形数据(多层级并列)
	 *
	 * @author 延晓磊
	 *
	 * @since 2017年6月12日
	 */
	public static <T extends TreeEntity<T, P>,P> Map<String, String> getTreeNameMap(List<T> list, P rootId) {
		return getTreeNameMap(list, rootId, null);
	}

	/**
	 * 将列表转换为树，多层级并列名称 - 根据sort排序
	 *
	 * @param list		列表
	 * @param rootId 	根节点
	 * @param rootName	根节点名称：默认null
	 *
	 * @return {'id':name} 树形数据(多层级并列)
	 *
	 * @author 延晓磊
	 *
	 * @since 2017年6月12日
	 */
	public static <T extends TreeEntity<T, P>,P> Map<String, String> getSortedTreeNameMap(List<T> list, P rootId, String rootName) {
		return getTreeNameMap(list, rootId, TreeSortComparator.get(), rootName);
	}

	/**
	 * 将列表转换为树，多层级并列名称 - 根据sort排序
	 *
	 * @param list		列表
	 * @param rootId 	根节点
	 *
	 * @return {'id':name} 树形数据(多层级并列)
	 *
	 * @author 延晓磊
	 *
	 * @since 2017年6月12日
	 */
	public static <T extends TreeEntity<T, P>,P> Map<String, String> getSortedTreeNameMap(List<T> list, P rootId) {
		return getSortedTreeNameMap(list, rootId, null);
	}

	/**
	 * 将列表转换为树，多层级并列，名称累加
	 *
	 * @param list		列表
	 * @param rootId 	根节点
	 * @param comparator	排序器
	 * @param rootName	根节点名称：默认null
	 *
	 * @return {'id':name} 树形数据(多层级并列)
	 *
	 * @author 延晓磊
	 *
	 * @since 2017年6月12日
	 */
	public static <T extends TreeEntity<T, P>,P> Map<String, T> getTreeMap(List<T> list, P rootId, Comparator<T> comparator, String rootName) {
		// 获取树型整理的list
		List<T> tree = getTree(list, rootId, comparator);
		// 并排树节点并组合名称
		Map<String,T> map = new LinkedHashMap<>();
		addChild(map, tree, rootName);
		return map;
	}

	/**
	 * 将列表转换为树，多层级并列，名称累加 - 默认顺序
	 *
	 * @param list		列表
	 * @param rootId 	根节点
	 * @param rootName	根节点名称：默认null
	 *
	 * @return {'id':name} 树形数据(多层级并列)
	 *
	 * @author 延晓磊
	 *
	 * @since 2017年6月12日
	 */
	public static <T extends TreeEntity<T, P>,P> Map<String, T> getTreeMap(List<T> list, P rootId, String rootName) {
		return getTreeMap(list, rootId, null, rootName);
	}

	/**
	 * 将列表转换为树，多层级并列，名称累加 - 默认顺序
	 *
	 * @param list		列表
	 * @param rootId 	根节点
	 *
	 * @return {'id':name} 树形数据(多层级并列)
	 *
	 * @author 延晓磊
	 *
	 * @since 2017年6月12日
	 */
	public static <T extends TreeEntity<T, P>,P> Map<String, T> getTreeMap(List<T> list, P rootId) {
		return getTreeMap(list, rootId, null);
	}

	/**
	 * 将列表转换为树，多层级并列，名称累加 - 根据sort排序
	 *
	 * @param list		列表
	 * @param rootId 	根节点
	 * @param rootName	根节点名称：默认null
	 *
	 * @return {'id':name} 树形数据(多层级并列)
	 *
	 * @author 延晓磊
	 *
	 * @since 2017年6月12日
	 */
	public static <T extends TreeEntity<T, P>,P> Map<String, T> getSortedTreeMap(List<T> list, P rootId, String rootName) {
		return getTreeMap(list, rootId, TreeSortComparator.get(), rootName);
	}

	/**
	 * 将列表转换为树，多层级并列，名称累加 - 根据sort排序
	 *
	 * @param list		列表
	 * @param rootId 	根节点
	 *
	 * @return {'id':name} 树形数据(多层级并列)
	 *
	 * @author 延晓磊
	 *
	 * @since 2017年6月12日
	 */
	public static <T extends TreeEntity<T, P>,P> Map<String, T> getSortedTreeMap(List<T> list, P rootId) {
		return getSortedTreeMap(list, rootId, null);
	}

	/**
	 * 将列表转换为树，多层级并列，添加根节点，名称累加
	 *
	 * @param list		列表
	 * @param rootId 	根节点
	 * @param comparator	排序器
	 * @param rootName	根节点名称：默认null
	 * @param root		根节点
	 *
	 * @return {'id':name} 树形数据(多层级并列)
	 *
	 * @author 延晓磊
	 *
	 * @since 2017年6月12日
	 */
	public static <T extends TreeEntity<T, P>,P> Map<String, T> getTreeRootMap(List<T> list, P rootId, Comparator<T> comparator, String rootName, T root) {
		// 获取树型整理的list
		List<T> tree = getTree(list, rootId, comparator);
		// 并排树节点并组合名称
		Map<String,T> map = new LinkedHashMap<>();
		if (root != null) {
			// 名称处理
			setChildName(root, rootName);
			rootName = root.getName();
			// 添加根节点
			map.put(root.getId().toString(), root);
		}
		addChild(map, tree, rootName);
		return map;
	}

	/**
	 * 将列表转换为树，多层级并列，添加根节点，名称累加 - 默认顺序
	 *
	 * @param list		列表
	 * @param rootId 	根节点
	 * @param rootName	根节点名称：默认null
	 * @param root		根节点
	 * @return {'id':name} 树形数据(多层级并列)
	 *
	 * @author 延晓磊
	 *
	 * @since 2017年6月12日
	 */
	public static <T extends TreeEntity<T, P>,P> Map<String, T> getTreeRootMap(List<T> list, P rootId, String rootName, T root) {
		return getTreeRootMap(list, rootId, null, rootName, root);
	}

	/**
	 * 将列表转换为树，多层级并列，添加根节点，名称累加 - 默认顺序
	 *
	 * @param list		列表
	 * @param rootId 	根节点
	 * @param root		根节点
	 * @return {'id':name} 树形数据(多层级并列)
	 *
	 * @author 延晓磊
	 *
	 * @since 2017年6月12日
	 */
	public static <T extends TreeEntity<T, P>,P> Map<String, T> getTreeRootMap(List<T> list, P rootId, T root) {
		return getTreeRootMap(list, rootId, null, root);
	}

	/**
	 * 将列表转换为树，多层级并列，添加根节点，名称累加 - 根据sort排序
	 *
	 * @param list		列表
	 * @param rootId 	根节点
	 * @param rootName	根节点名称：默认null
	 * @param root		根节点
	 * @return {'id':name} 树形数据(多层级并列)
	 *
	 * @author 延晓磊
	 *
	 * @since 2017年6月12日
	 */
	public static <T extends TreeEntity<T, P>,P> Map<String, T> getSortedTreeRootMap(List<T> list, P rootId, String rootName, T root) {
		return getTreeRootMap(list, rootId, TreeSortComparator.get(), rootName, root);
	}

	/**
	 * 将列表转换为树，多层级并列，添加根节点，名称累加 - 根据sort排序
	 *
	 * @param list		列表
	 * @param rootId 	根节点
	 * @param root		根节点
	 * @return {'id':name} 树形数据(多层级并列)
	 *
	 * @author 延晓磊
	 *
	 * @since 2017年6月12日
	 */
	public static <T extends TreeEntity<T, P>,P> Map<String, T> getSortedTreeRootMap(List<T> list, P rootId, T root) {
		return getSortedTreeRootMap(list, rootId, null, root);
	}

	/**
	 * 过滤树列表，保留3级满子树
	 *
	 * @param list	树型列表
	 * @param <T>
	 * @param <P>
	 * @return
	 *
	 * @author 延晓磊
	 * @since 2021年01月20日
	 */
	public static <T extends TreeEntity<T, P>,P>List<T> filter3(List<T> list){
		if (!list.isEmpty()) {
			List<T> root = new ArrayList<>(list.size());
			List<T> tmp;
			// 1级
			for (T c1 : list) {
				// 有2级
				if (CollectionUtils.isNotEmpty(c1.getChildren())) {
					tmp = new ArrayList<>(c1.getChildren().size());
					for (T c2 : c1.getChildren()) {
						// 有3级
						if (CollectionUtils.isNotEmpty(c2.getChildren())) {
							// 满子树的2级
							tmp.add(c2);
						}
					}
					// 有2+3级
					if (!tmp.isEmpty()) {
						// 满子树的1级
						c1.setChildren(tmp);
						root.add(c1);
					}
				}
			}
			list = root;
		}
		return list;
	}

	/**
	 * 将树转换为列表（并排树节点，清除children）
	 *
	 * @param tree
	 * @param <T>
	 * @param <P>
	 * @return
	 *
	 * @author 延晓磊
	 * @since 2021年09月28日
	 */
	public static <T extends TreeEntity<T, P>,P>List<T> toList(List<T> tree) {
		List<T> nodes = new ArrayList<>();
		addChild(nodes, tree);
		return nodes;
	}

	/**
	 * 将树转换为列表（并排树节点，不清除children）
	 *
	 * @param tree
	 * @param <T>
	 * @param <P>
	 * @return
	 *
	 * @author 延晓磊
	 * @since 2021年09月28日
	 */
	public static <T extends TreeEntity<T, P>,P>List<T> toListKeepChildren(List<T> tree) {
		List<T> nodes = new ArrayList<>();
		addChildKeepChildren(nodes, tree);
		return nodes;
	}

	/**
	 * 设置树型数据的title字段，以/分隔
	 *
	 * @param tree
	 * @param rootName	根节点名称
	 * @param <T>
	 * @param <P>
	 * @return
	 *
	 * @author 延晓磊
	 * @since 2021年09月28日
	 */
	public static <T extends TreeEntity<T, P>,P>List<T> addTitle(List<T> tree, String rootName) {
		// 根节点名称
		if (StringUtils.isNotBlank(rootName)) {
			rootName = rootName + StringConstant.SEPARATOR;
		}else{
			rootName = null;
		}
		for (T o : tree) {
		   // 一级
		   o.setTitle(rootName == null ? o.getName() : rootName + o.getName());
		   // 子级
		   if (CollectionUtils.isNotEmpty(o.getChildren())) {
		   	  	setChildTitle(o.getChildren(), o);
		   }
		}
		return tree;
	}

	/**
	 * 设置树型数据的tree_id字段，以,分隔
	 *
	 * @param tree
	 * @param rootId	根节点ID
	 * @param <T>
	 * @param <P>
	 * @return
	 *
	 * @author 延晓磊
	 * @since 2021年09月28日
	 */
	public static <T extends TreeEntity<T, P>,P>List<T> addTreeId(List<T> tree, P rootId) {
		for (T o : tree) {
			// 一级
			o.setTreeId(rootId == null ? o.getId().toString() : rootId  +StringConstant.COMMA+ o.getId());
			// 子级
			if (CollectionUtils.isNotEmpty(o.getChildren())) {
				setChildTreeId(o.getChildren(), o);
			}
		}
		return tree;
	}

	/**
	 * 获取树的头
	 *
	 * @param tree	树
	 * @param headId	头的id
	 * @param <T>
	 * @param <P>
	 * @return	头数据，未找到返回null
	 */
	public static <T extends TreeEntity<T, P>,P>T getHead(List<T> tree, P headId) {
		if (headId == null || CollectionUtils.isEmpty(tree)) {
			return null;
		}
		// 并排
		List<T> all = toListKeepChildren(tree);
		// 查询头
		for (T t : all) {
		    if (t.getId().equals(headId)) {
		    	return t;
		    }
		}
		return null;
	}

	/**
	 * 获取树的链
	 *
	 * @param tree	树
	 * @param headId	树头
	 * @param <T>
	 * @param <P>
	 * @return List<T>
	 */
	public static <T extends TreeEntity<T, P>,P>List<T> getChain(List<T> tree, P headId) {
		// 获取树头
		T head = TreeUtil.getHead(tree, headId);
		if (head == null) {
			return new ArrayList<>();
		}else{
			// 转为列表
			return TreeUtil.toList(CollectionUtil.toList(head));
		}
	}

	/**
	 * 获取树的链
	 *
	 * @param tree	树
	 * @param headId	树头
	 * @param fn	链结果
	 * @param <T>
	 * @param <P>
	 * @param <R>
	 * @return List<R>
	 */
	public static <T extends TreeEntity<T, P>,P,R>List<R> getChain(List<T> tree, P headId, Function<T,R> fn) {
		// 获取树头
		T head = TreeUtil.getHead(tree, headId);
		if (head == null) {
			return new ArrayList<>();
		}else{
			// 转为列表
			return TreeUtil.toList(CollectionUtil.toList(head)).stream().map(fn).collect(Collectors.toList());
		}
	}

	/**
	 * 获取树的链
	 *
	 * @param tree	树
	 * @param headId	树头
	 * @param <T>
	 * @param <P>
	 * @return List<P>
	 */
	public static <T extends TreeEntity<T, P>,P>List<P> getIdChain(List<T> tree, P headId) {
		return getChain(tree, headId, TreeEntity::getId);
	}

	/**
	 * 遍历树
	 *
	 * @param tree	树列表
	 * @param consumer	遍历处理
	 * @return 树
	 *
	 * @author 延晓磊
	 * @since 2023年01月20日
	 */
	public static <T extends TreeEntity<T, P>, P>List<T> forEach(List<T> tree, Consumer<T> consumer){
		tree.forEach(o ->{
			consumer.accept(o);
			if (CollectionUtils.isNotEmpty(o.getChildren())) {
				forEach(o.getChildren(), consumer);
			}
		});
		return tree;
	}

	/**
	 * 递归查找数据（单个）
	 *
	 * @param tree		树列表
	 * @param predicate	查找条件
	 * @return 结果数据
	 */
	public static  <T extends TreeEntity<T, P>,P>T find(List<T> tree, Predicate<T> predicate){
		T result;
		for (T t : tree) {
		    if (predicate.test(t)) {
		    	return t;
		    }else if (CollectionUtils.isNotEmpty(t.getChildren())) {
		    	result = find(t.getChildren(), predicate);
		    	if (result != null) {
		    		return result;
		    	}
		    }
		}
		return null;
	}

	/**
	 * 递归查找数据（多个）
	 *
	 * @param tree		树列表
	 * @param predicate	查找条件
	 * @param list		结果列表
	 * @return 结果列表
	 */
	public static  <T extends TreeEntity<T, P>,P>List<T> find(List<T> tree, Predicate<T> predicate, List<T> list){
		forEach(tree, o -> {
			if (predicate.test(o)) {
				list.add(o);
			}
		});
		return list;
	}

	/**
	 * 递归过滤数据（保留上级，变更原树，返回原树）
	 *
	 * @param tree		树列表（children会被变更，不能二次使用）
	 * @param predicate	过滤条件
	 *
	 * @return [过滤后的数据；如果数据存在，将保留数据及上级]
	 */
	public static  <T extends TreeEntity<T, P>,P>List<T> filter(List<T> tree, Predicate<T> predicate){
		return tree.stream().filter(o ->{
			boolean bool = false;
			// 当前节点
			if (predicate.test(o)) {
				bool = true;
			}else if (CollectionUtils.isNotEmpty(o.getChildren())) {
				bool = find(o.getChildren(), predicate) != null;
			}
			// 递归
			if (bool && CollectionUtils.isNotEmpty(o.getChildren())) {
				o.setChildren(filter(o.getChildren(), predicate));
			}
			return bool;
		}).collect(Collectors.toList());
	}

	/**
	 * 递归过滤数据（保留上级，不变更原树，返回新树）
	 *
	 * @param tree		树列表（根据isNew判断是否会被变更）
	 * @param predicate	过滤条件
	 * @param isNew	是否返回新列表，而不变更原列表
	 *
	 * @return [过滤后的数据；如果数据存在，将保留数据及上级]
	 */
	public static  <T extends TreeEntity<T, P>,P>List<T> filter(List<T> tree, Predicate<T> predicate, boolean isNew){
		if (isNew) {
			// 返回新数据
			List<T> newTree = new ArrayList<>(tree.size());
			T newNode;
			for (T node : tree) {
				// 当前节点
				if (predicate.test(node) || find(node.getChildren(), predicate) != null) {
					newNode = ReflectUtil.clone(node);
					newTree.add(newNode);
					// 子节点
					if (CollectionUtils.isNotEmpty(node.getChildren())) {
						newNode.setChildren(filter(node.getChildren(), predicate, isNew));
					}
				}
			}
			return newTree;
		}else{
			// 变更原数据
			return filter(tree, predicate);
		}

	}

	/**
	 * 递归过滤数据（保留上级，不变更原树，返回新列表）
	 *
	 * @param tree		树列表（根据isNew判断是否会被变更）
	 * @param predicate	过滤条件
	 * @param list		结果列表
	 * @return 结果列表
	 */
	public static  <T extends TreeEntity<T, P>,P>List<T> filter(List<T> tree, Predicate<T> predicate, List<T> list){
		forEach(tree, o ->{
			boolean bool = false;
			if (predicate.test(o)) {
				bool = true;
			}else if (CollectionUtils.isNotEmpty(o.getChildren())) {
				bool = find(o.getChildren(), predicate) != null;
			}
			if (bool) {
				list.add(o);
			}
		});
		return list;
	}

	/**
	 * 将子节点并排加入根list（清除children）
	 * 
	 * @param rootList 根List
	 * @param list	当前节点列表
	 * 
	 * @author 延晓磊
	 *
	 * @since 2018年12月28日
	 */
	private static <T extends TreeEntity<T, P>, P> void addChild(List<T> rootList, List<T> list) {
		for (T t : list) {
			rootList.add(t);
			if (CollectionUtils.isNotEmpty(t.getChildren())) {
				addChild(rootList, t.getChildren());
			}
			t.setChildren(null);
		}
	}

	/**
	 * 将子节点并排加入根list（不清除children）
	 *
	 * @param rootList 根List
	 * @param list	当前节点列表
	 *
	 * @author 延晓磊
	 *
	 * @since 2018年12月28日
	 */
	private static <T extends TreeEntity<T, P>, P> void addChildKeepChildren(List<T> rootList, List<T> list) {
		for (T t : list) {
			rootList.add(t);
			if (CollectionUtils.isNotEmpty(t.getChildren())) {
				addChildKeepChildren(rootList, t.getChildren());
			}
		}
	}

	/**
	 * 将子节点并排加入根Map，累积节点名称
	 *
	 * @param rootMap 根Map
	 * @param list	当前节点列表
	 * @param parentName	父名称
	 *
	 * @author 延晓磊
	 *
	 * @since 2018年12月28日
	 */
	private static <T extends TreeEntity<T, P>, P> void addChild(Map<String, T> rootMap, List<T> list, String parentName) {
		for (T t : list) {
			// 名称
			setChildName(t,parentName);
			rootMap.put(t.getId().toString(), t);
			// 递归
			if (CollectionUtils.isNotEmpty(t.getChildren())) {
				addChild(rootMap, t.getChildren(), t.getName());
			}
		}
	}

	/**
	 * 将子节点并排加入根Map，只保留累积名称
	 * 
	 * @param rootMap 根Map
	 * @param list	当前节点列表
	 * @param parentName	父名称
	 * 
	 * @author 延晓磊
	 *
	 * @since 2018年12月28日
	 */
	private static <T extends TreeEntity<T, P>, P> void addChildName(Map<String, String> rootMap, List<T> list, String parentName) {
		for (T t : list) {
			// 名称
			setChildName(t,parentName);
			rootMap.put(t.getId().toString(), t.getName());
			// 递归
			if (CollectionUtils.isNotEmpty(t.getChildren())) {
				addChildName(rootMap, t.getChildren(), t.getName());
			}
		}
	}

	/**
	 * 设置节点的并列名称
	 *
	 * @param t  节点
	 * @param parentName  父名称
	 *
	 * @author 延晓磊
	 *
	 * @since 2018年12月28日
	 */
	private static <T extends TreeEntity<T, P>, P> void setChildName(T t, String parentName) {
		if (StringUtils.isNotBlank(parentName)) {
			if(StringConstant.SEPARATOR.equals(parentName)){
				t.setName(parentName + t.getName());
			}else{
				t.setName(parentName + StringConstant.SEPARATOR + t.getName());
			}
		}
	}

	/**
	 * 设置子节点的标题
	 *
	 * @param children
	 * @param parent
	 * @param <T>
	 * @param <P>
	 *
	 * @author 延晓磊
	 * @since 2021年09月28日
	 */
	private static <T extends TreeEntity<T, P>, P>void setChildTitle(List<T> children, T parent) {
		for (T o : children) {
			// 一级
			o.setTitle(parent.getName() + StringConstant.SEPARATOR + o.getName());
			// 子级
			if (CollectionUtils.isNotEmpty(o.getChildren())) {
				setChildTitle(o.getChildren(), o);
			}
		}
	}

	/**
	 * 设置子节点的treeId
	 *
	 * @param children
	 * @param parent
	 * @param <T>
	 * @param <P>
	 *
	 * @author 延晓磊
	 * @since 2021年09月28日
	 */
	private static <T extends TreeEntity<T, P>, P>void setChildTreeId(List<T> children, T parent) {
		for (T o : children) {
			// 一级
			o.setTreeId(parent.getTreeId() + StringConstant.COMMA + o.getId());
			// 子级
			if (CollectionUtils.isNotEmpty(o.getChildren())) {
				setChildTreeId(o.getChildren(), o);
			}
		}
	}
}
